package algorithm.backtracking.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author yuisama
 * @date 2023年07月14日 14:00
 * @description 回溯之字符串组合问题2。包含重复元素的组合问题
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 */
public class Offer38_StringPermutation {
    public String[] permutation(String s) {
        // 可以选择的字符
        char[] choices = s.toCharArray();
        // 相同元素排列在一起
        Arrays.sort(choices);
        // 存储当前哪个字符使用过
        boolean[] used = new boolean[s.length()];
        // 当前已选择的元素状态
        LinkedList<Character> state = new LinkedList<>();
        // 结果集
        List<String> res = new LinkedList<>();
        backTracking(res,used,choices,state);
        // 将List转为字符串数组
        return res.toArray(new String[0]);
    }

    private void backTracking(List<String> res, boolean[] used, char[] choices, LinkedList<Character> state) {
        if (state.size() == choices.length) {
            // 做完本轮组合，添加到结果集
            // 将List集合内容转为字符串
            String result = state.stream()
                            .map(String::valueOf)
                            .collect(Collectors.joining());
            res.add(result);
            return;
        }
        // 枚举每个字符
        for (int i = 0; i < choices.length; i++) {
            // 做出选择
            char c = choices[i];
            if (used[i]) {
                continue;
            }
            // 剪枝，固定相同元素在数组中的位置
            // 关于此处剪枝的说明
            // 以"abb"为例，当第一位选取第二个'a'时，后续选择都需要剪枝，因为和选取第一个'a'重复
            // 因此choices[i] == choices[i - 1] 表示此处字符和前一个相同
            // 且 !used[i - 1] == true表示先选用的是后面的重复元素，一定构成重复结果集，剪枝！
            if (i > 0 && choices[i] == choices[i - 1] && ! used[i - 1]) {
                continue;
            }
            // 当前字符还没用过，添加到状态中
            used[i] = true;
            state.add(c);
            // 继续枚举剩下的字符
            backTracking(res, used, choices, state);
            // 撤销选择
            used[i] = false;
            state.removeLast();
        }
    }
}
